1513-仅含 1 的子串数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给你一个二进制字符串 s（仅由 ‘0’ 和 ‘1’ 组成的字符串）。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

示例 1：

**输入：** s = "0110111"
**输出** ：9
**解释：** 共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次

示例 2：

**输入：** s = "101"
**输出：** 2
**解释：** 子字符串 "1" 在 s 中共出现 2 次

示例 3：

**输入：** s = "111111"
**输出：** 21
**解释：** 每个子字符串都仅由 '1' 组成

示例 4：

**输入：** s = "000"
**输出：** 0

提示：

  • s[i] == '0' 或 s[i] == '1'
  • 1 <= s.length <= 10^5

方法一：遍历字符串寻找最长子串

如果一个所有字符都为 1 的字符串的长度为 k，则该字符串包含的所有字符都为 1 的子字符串（包括该字符串本身）的数量是 k * (k + 1) / 2。

首先寻找到所有的只包含字符 1 的最长子字符串。这里的「只包含字符 1 的最长子字符串」的意思是，假设该子字符串的下标范围是 [i, j]（包含下标 i 和下标 j），其中 i <= j，该子字符串中的所有字符都是 1，且下标 i 满足 i 位于字符串 s 的最左侧或者下标 i - 1 位置的字符是 0，以及下标 j 满足 j 位于字符串 s 的最右侧或者下标 j + 1 位置的字符是 0。

寻找到所有的只包含字符 1 的最长子字符串之后，就可以计算所有字符都为 1 的子字符串的数量。

具体做法是，从左到右遍历字符串，如果遇到字符 1 则计算连续字符 1 的数量，如果遇到字符 0 则说明上一个只包含字符 1 的最长子字符串遍历结束，根据最长子字符串的长度计算子字符串的数量，然后将连续字符 1 的数量清零。遍历结束后，如果连续字符 1 的数量大于零，则还有最后一个只包含字符 1 的最长子字符串，因此还需要计算其对应的子字符串的数量。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numSub(String s) {
        final int MODULO = 1000000007;
        long total = 0;
        int length = s.length();
        long consecutive = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == '0') {
                total += consecutive * (consecutive + 1) / 2;
                total %= MODULO;
                consecutive = 0;
            } else {
                consecutive++;
            }
        }
        total += consecutive * (consecutive + 1) / 2;
        total %= MODULO;
        return (int) total;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static constexpr int P = int(1E9) + 7;
    
    int numSub(string s) {
        int p = 0;
        long long ans = 0;
        while (p < s.size()) {
            if (s[p] == '0') {
                ++p;
                continue;
            }
            int cnt = 0;
            while (p < s.size() && s[p] == '1') {
                ++cnt;
                ++p;
            }
            ans = ans + (1LL + (long long)cnt) * cnt / 2;
            ans = ans % P;
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numSub(self, s: str) -> int:
        total, consecutive = 0, 0
        length = len(s)
        for i in range(length):
            if s[i] == '0':
                total += consecutive * (consecutive + 1) // 2
                consecutive = 0
            else:
                consecutive += 1
        
        total += consecutive * (consecutive + 1) // 2
        total %= (10**9 + 7)
        return total

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串一次。

  • 空间复杂度：O(1)。只需要维护有限的变量，空间复杂度是常数。

 Comments
On this page
1513-仅含 1 的子串数